from collections import deque
from typing import List

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        m= len(grid)
        n = len(grid[0])
        inf = float('inf')
        minues = [[inf for _ in range(n)] for _ in range(m)]

        queue = deque()
        count = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j]==2:
                    minues[i][j] = 0
                    queue.append((i,j))
                elif grid[i][j]==1:
                    count += 1
        time = 0
        while queue:
            col,row = queue.popleft()
            for ncol,nrow in [(col+1,row),(col-1,row),(col,row+1),(col,row-1)]:
                if ncol <0 or ncol>=m: continue
                if nrow <0 or nrow>=n: continue
                if grid[ncol][nrow]!=1: continue
                minues[ncol][nrow] = minues[col][row]+1
                time = minues[ncol][nrow]
                grid[ncol][nrow]=2
                queue.append((ncol,nrow))
                count -= 1

        if count != 0: return -1
        return time


if __name__ == "__main__":
    s = Solution()
    s.orangesRotting([[2,1,1],[1,1,0],[0,1,1]])